package com.fe.class01;

import java.util.Arrays;

/**
 * @Description 在一个有序数组中，找大于等于某个数最左侧的位置
 * @Author sosuke :-)
 * @Date 2021/12/1 21:21
 */
public class Code05_BSNearLeft {

    /**
     * 在arr上，找满足>=value的最左位置
     *
     * @param arr
     * @param value
     * @return
     */
    public static int nearestLeftIndex(int[] arr, int value) {
        if (null == arr) return -1;
        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 默认表示不存在
        while (L <= R) { // 至少一个数的时候
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {
                index = mid;
                R = mid - 1; // 左侧可能还有大于等于value的，向左移
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);
            int value = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
            int res1 = nearestLeftIndex(arr, value);
            int res2 = testNearestLeftIndex(arr, value);
            if (res1 != res2) {
                succeed = false;
                System.out.println("arr = " + Arrays.toString(arr));
                System.out.println("value = " + value);
                System.out.println("res1 = " + res1);
                System.out.println("res2 = " + res2);
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
        int[] arr = generateRandomArray(maxSize, maxValue);
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        int num = (int) (Math.random() * (maxValue + 1) - Math.random() * (maxValue));
        System.out.println("find num = " + num);
        System.out.println("res = " + nearestLeftIndex(arr, num));
    }

    private static int testNearestLeftIndex(int[] arr, int value) {
        if (null == arr) return -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= value) {
                return i;
            }
        }
        return -1;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
        }
        return arr;
    }
}
